Termination w.r.t. Q proof of /tmp/tmpn57I5n/#3.42.trs

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
lastbit(0) → 0
lastbit(s(0)) → s(0)
lastbit(s(s(x))) → lastbit(x)
conv(0) → cons(nil, 0)
conv(s(x)) → cons(conv(half(s(x))), lastbit(s(x)))

Q is empty.

↳ QTRS

  ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
lastbit(0) → 0
lastbit(s(0)) → s(0)
lastbit(s(s(x))) → lastbit(x)
conv(0) → cons(nil, 0)
conv(s(x)) → cons(conv(half(s(x))), lastbit(s(x)))

Q is empty.

Using Dependency Pairs [1,15] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

HALF(s(s(x))) → HALF(x)
CONV(s(x)) → LASTBIT(s(x))
CONV(s(x)) → CONV(half(s(x)))
LASTBIT(s(s(x))) → LASTBIT(x)
CONV(s(x)) → HALF(s(x))

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
lastbit(0) → 0
lastbit(s(0)) → s(0)
lastbit(s(s(x))) → lastbit(x)
conv(0) → cons(nil, 0)
conv(s(x)) → cons(conv(half(s(x))), lastbit(s(x)))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

HALF(s(s(x))) → HALF(x)
CONV(s(x)) → LASTBIT(s(x))
CONV(s(x)) → CONV(half(s(x)))
LASTBIT(s(s(x))) → LASTBIT(x)
CONV(s(x)) → HALF(s(x))

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
lastbit(0) → 0
lastbit(s(0)) → s(0)
lastbit(s(s(x))) → lastbit(x)
conv(0) → cons(nil, 0)
conv(s(x)) → cons(conv(half(s(x))), lastbit(s(x)))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 3 SCCs with 2 less nodes.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

            ↳ QDPOrderProof

          ↳ QDP

          ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

LASTBIT(s(s(x))) → LASTBIT(x)

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
lastbit(0) → 0
lastbit(s(0)) → s(0)
lastbit(s(s(x))) → lastbit(x)
conv(0) → cons(nil, 0)
conv(s(x)) → cons(conv(half(s(x))), lastbit(s(x)))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].

The following pairs can be oriented strictly and are deleted.

LASTBIT(s(s(x))) → LASTBIT(x)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Polynomial interpretation [25,35]:

POL(LASTBIT(x₁)) = (1/2)x_1
POL(s(x₁)) = 1/4 + x_1

The value of delta used in the strict ordering is 1/4.
The following usable rules [17] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

            ↳ QDPOrderProof

              ↳ QDP

                ↳ PisEmptyProof

          ↳ QDP

          ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
lastbit(0) → 0
lastbit(s(0)) → s(0)
lastbit(s(s(x))) → lastbit(x)
conv(0) → cons(nil, 0)
conv(s(x)) → cons(conv(half(s(x))), lastbit(s(x)))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

            ↳ QDPOrderProof

          ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

HALF(s(s(x))) → HALF(x)

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
lastbit(0) → 0
lastbit(s(0)) → s(0)
lastbit(s(s(x))) → lastbit(x)
conv(0) → cons(nil, 0)
conv(s(x)) → cons(conv(half(s(x))), lastbit(s(x)))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].

The following pairs can be oriented strictly and are deleted.

HALF(s(s(x))) → HALF(x)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Polynomial interpretation [25,35]:

POL(HALF(x₁)) = x_1
POL(s(x₁)) = 5/4 + (5/2)x_1

The value of delta used in the strict ordering is 35/8.
The following usable rules [17] were oriented: none

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

            ↳ QDPOrderProof

              ↳ QDP

                ↳ PisEmptyProof

          ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
lastbit(0) → 0
lastbit(s(0)) → s(0)
lastbit(s(s(x))) → lastbit(x)
conv(0) → cons(nil, 0)
conv(s(x)) → cons(conv(half(s(x))), lastbit(s(x)))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

          ↳ QDP

            ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

CONV(s(x)) → CONV(half(s(x)))

The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
lastbit(0) → 0
lastbit(s(0)) → s(0)
lastbit(s(s(x))) → lastbit(x)
conv(0) → cons(nil, 0)
conv(s(x)) → cons(conv(half(s(x))), lastbit(s(x)))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].

The following pairs can be oriented strictly and are deleted.

CONV(s(x)) → CONV(half(s(x)))

The remaining pairs can at least be oriented weakly.
none
Used ordering: Polynomial interpretation [25,35]:

POL(half(x₁)) = (3/4)x_1
POL(CONV(x₁)) = (13/4)x_1
POL(s(x₁)) = 3/4 + (13/4)x_1
POL(0) = 0

The value of delta used in the strict ordering is 39/64.
The following usable rules [17] were oriented:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

          ↳ QDP

            ↳ QDPOrderProof

              ↳ QDP

                ↳ PisEmptyProof

Q DP problem:
P is empty.
The TRS R consists of the following rules:

half(0) → 0
half(s(0)) → 0
half(s(s(x))) → s(half(x))
lastbit(0) → 0
lastbit(s(0)) → s(0)
lastbit(s(s(x))) → lastbit(x)
conv(0) → cons(nil, 0)
conv(s(x)) → cons(conv(half(s(x))), lastbit(s(x)))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.